//import javafx.util.Pair;
//
//import java.util.*;
//import java.util.function.ToIntFunction;
//import java.util.stream.Stream;
//
//enum Color {
//    RED,
//    BLACK
//}
//
//class Node {
//    int value;
//    Color color;
//    Node left;
//    Node right;
//    Node parent;
//
//    public Node(int value) {
//        this.value = value;
//        this.color = Color.RED;
//        this.left = null;
//        this.right = null;
//        this.parent = null;
//    }
//}
//
//class RedBlackTree {
//    private Node root;
//
//    /**
//     * "nil" 是一个特殊的节点，也被称为哨兵节点或空节点。
//     * 它不存储任何实际的数据，只用于表示 空位置或边界。在红黑树中，所有的叶子节点都被表示为 nil 节点。
//     * nil 节点的颜色通常被定义为黑色，以满足红黑树的性质。
//     * nil 节点的存在有助于简化红黑树的实现和操作。
//     * 它可以作为叶子节点的父节点，使得所有的叶子节点都具有相同的黑色深度。
//     * 同时，nil 节点也可以作为节点的子节点，使得在旋转操作中不需要处理空指针的情况。
//     */
//    // 后面所有的 nil的效果都等于 null，以后不再区分
//    private Node nil;
//
//    /**
//     * 用于初始化 nil节点
//     */
//    public RedBlackTree() {
//        // nil的值并不重要
//        this.nil = new Node(0);
//        // nil的颜色为黑
//        this.nil.color = Color.BLACK;
//        // 如果没有节点，nil就作为根节点，实际就是空节点的意思
//        this.root = this.nil;
//    }
//
//    public void insert(int value) {
//        // 先找到新节点应该插入的位置（和AVL树相同）
//        Node newNode = new Node(value);
//        // 还未找到，所以新节点的 parent为 nil（null）
//        Node parent = this.nil;
//        // 从根节点 root开始寻找
//        Node current = this.root;
//        // 如果当前节点 current不为 nil（null），继续搜索
//        while (current != this.nil) {
//            parent = current;// 更新 parent
//            if (value < current.value)// 插入左边
//                current = current.left;
//            else if (value > current.value)// 插入右边
//                current = current.right;
//            else // 相等直接返回
//                return;
//        }
//        // 更新新节点的 parent
//        newNode.parent = parent;
//        if (parent == this.nil) // 如果 parent为 nil，说明该节点为 root
//            this.root = newNode;
//        else if (value < parent.value) // 如果插入的值小于 parent的值，说明它是 parent的 left
//            parent.left = newNode;
//        else // 同理是右子树
//            parent.right = newNode;
//        // 新节点的左右子树都为 nil，默认颜色为 RED
//        newNode.left = this.nil;
//        newNode.right = this.nil;
//        newNode.color = Color.RED;
//        // 然后更新节点的颜色和旋转分支
//        insertFixup(newNode);
//    }
//
//    /**
//     * 三种情况
//     *
//     * @param node
//     */
//    private void insertFixup(Node node) {
//        while (node.parent.color == Color.RED)
//            if (node.parent == node.parent.parent.left) {
//                Node uncle = node.parent.parent.right;
//                if (uncle.color == Color.RED) {// 情况一
//                    node.parent.color = Color.BLACK;
//                    uncle.color = Color.BLACK;
//                    node.parent.parent.color = Color.RED;
//                    node = node.parent.parent;
//                } else {// 情况三 的 ①
//                    if (node == node.parent.right) {
//                        node = node.parent;
//                        leftRotate(node);
//                    }
//                    // 情况二 的 ①
//                    node.parent.color = Color.BLACK;
//                    node.parent.parent.color = Color.RED;
//                    rightRotate(node.parent.parent);
//                }
//            } else {
//                Node uncle = node.parent.parent.left;
//                if (uncle.color == Color.RED) {// 情况一
//                    node.parent.color = Color.BLACK;
//                    uncle.color = Color.BLACK;
//                    node.parent.parent.color = Color.RED;
//                    node = node.parent.parent;
//                } else {// 情况三 的 ②
//                    if (node == node.parent.left) {
//                        node = node.parent;
//                        rightRotate(node);
//                    }
//                    // 情况二 的 ②
//                    node.parent.color = Color.BLACK;
//                    node.parent.parent.color = Color.RED;
//                    leftRotate(node.parent.parent);
//                }
//            }
//        // 无论如何 root.color都是 BLACK，任何情况都是，所以直接全部应用
//        this.root.color = Color.BLACK;
//    }
//
//    private void leftRotate(Node node) {
//        Node rightChild = node.right;
//        node.right = rightChild.left;
//        if (rightChild.left != this.nil) {
//            rightChild.left.parent = node;
//        }
//        rightChild.parent = node.parent;
//        if (node.parent == this.nil) {
//            this.root = rightChild;
//        } else if (node == node.parent.left) {
//            node.parent.left = rightChild;
//        } else {
//            node.parent.right = rightChild;
//        }
//        rightChild.left = node;
//        node.parent = rightChild;
//    }
//
//    private void rightRotate(Node node) {
//        Node leftChild = node.left;
//        node.left = leftChild.right;
//        if (leftChild.right != this.nil) {
//            leftChild.right.parent = node;
//        }
//        leftChild.parent = node.parent;
//        if (node.parent == this.nil) {
//            this.root = leftChild;
//        } else if (node == node.parent.right) {
//            node.parent.right = leftChild;
//        } else {
//            node.parent.left = leftChild;
//        }
//        leftChild.right = node;
//        node.parent = leftChild;
//    }
//
//    public void inorderTraversal() {
//        inorderTraversal(this.root);
//    }
//
//    private void inorderTraversal(Node root) {
//        if (root != this.nil) {
//            inorderTraversal(root.left);
//            System.out.print(root.value + " ");
//            inorderTraversal(root.right);
//        }
//    }
//
//
//    //=================================================================================================================
//    // 以下为删除操作仅作了解即可
//
//
//    public void delete(int value) {
//        Node node = search(value);
//        if (node == null) {
//            return; // 要删除的节点不存在
//        }
//
//        Node y = node;
//        Node x;
//        Color yOriginalColor = y.color;
//
//        if (node.left == nil) {
//            x = node.right;
//            transplant(node, node.right);
//        } else if (node.right == nil) {
//            x = node.left;
//            transplant(node, node.left);
//        } else {
//            y = minimum(node.right);
//            yOriginalColor = y.color;
//            x = y.right;
//            if (y.parent == node) {
//                x.parent = y;
//            } else {
//                transplant(y, y.right);
//                y.right = node.right;
//                y.right.parent = y;
//            }
//            transplant(node, y);
//            y.left = node.left;
//            y.left.parent = y;
//            y.color = node.color;
//        }
//
//        if (yOriginalColor == Color.BLACK) {
//            deleteFixup(x);
//        }
//    }
//
//    private void transplant(Node u, Node v) {
//        if (u.parent == nil) {
//            root = v;
//        } else if (u == u.parent.left) {
//            u.parent.left = v;
//        } else {
//            u.parent.right = v;
//        }
//        v.parent = u.parent;
//    }
//
//    private void deleteFixup(Node node) {
//        while (node != root && node.color == Color.BLACK) {
//            if (node == node.parent.left) {
//                Node sibling = node.parent.right;
//                if (sibling.color == Color.RED) {
//                    sibling.color = Color.BLACK;
//                    node.parent.color = Color.RED;
//                    leftRotate(node.parent);
//                    sibling = node.parent.right;
//                }
//                if (sibling.left.color == Color.BLACK && sibling.right.color == Color.BLACK) {
//                    sibling.color = Color.RED;
//                    node = node.parent;
//                } else {
//                    if (sibling.right.color == Color.BLACK) {
//                        sibling.left.color = Color.BLACK;
//                        sibling.color = Color.RED;
//                        rightRotate(sibling);
//                        sibling = node.parent.right;
//                    }
//                    sibling.color = node.parent.color;
//                    node.parent.color = Color.BLACK;
//                    sibling.right.color = Color.BLACK;
//                    leftRotate(node.parent);
//                    node = root;
//                }
//            } else {
//                Node sibling = node.parent.left;
//                if (sibling.color == Color.RED) {
//                    sibling.color = Color.BLACK;
//                    node.parent.color = Color.RED;
//                    rightRotate(node.parent);
//                    sibling = node.parent.left;
//                }
//                if (sibling.right.color == Color.BLACK && sibling.left.color == Color.BLACK) {
//                    sibling.color = Color.RED;
//                    node = node.parent;
//                } else {
//                    if (sibling.left.color == Color.BLACK) {
//                        sibling.right.color = Color.BLACK;
//                        sibling.color = Color.RED;
//                        leftRotate(sibling);
//                        sibling = node.parent.left;
//                    }
//                    sibling.color = node.parent.color;
//                    node.parent.color = Color.BLACK;
//                    sibling.left.color = Color.BLACK;
//                    rightRotate(node.parent);
//                    node = root;
//                }
//            }
//        }
//        node.color = Color.BLACK;
//    }
//
//    private Node minimum(Node node) {
//        while (node.left != nil) {
//            node = node.left;
//        }
//        return node;
//    }
//
//    private Node search(int value) {
//        Node current = root;
//        while (current != nil) {
//            if (value == current.value) {
//                return current;
//            } else if (value < current.value) {
//                current = current.left;
//            } else {
//                current = current.right;
//            }
//        }
//        return null; // 节点不存在
//    }
//
//
//    public static void main(String[] args) {
//        RedBlackTree rbTree = new RedBlackTree();
//        System.out.println(rbTree.nil.value);
//
//        // 16, 3, 7, 11, 9, 26, 18, 14, 15
//        rbTree.insert(16);
//        rbTree.insert(16);
//        rbTree.insert(7);
//        rbTree.insert(11);
//        rbTree.insert(9);
//        rbTree.insert(26);
//        rbTree.insert(18);
//        rbTree.insert(14);
//        rbTree.insert(15);
//
//        System.out.println("中序遍历结果：");
//        rbTree.inorderTraversal();
//        System.out.println();
//        rbTree.delete(26);
//        rbTree.inorderTraversal();
//    }
//}
//
//public class Ceshi {
//    public static void main(String[] args) {
//        RedBlackTree.main(args);
//    }
//}
//
//
//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode() {
//    }
//
//    ListNode(int val) {
//        this.val = val;
//    }
//
//    ListNode(int val, ListNode next) {
//        this.val = val;
//        this.next = next;
//    }
//}
//
//class Solution {
//    public ListNode mergeKLists(ListNode[] lists) {
//        if (lists == null)
//            return null;
//        PriorityQueue<ListNode> heap = new PriorityQueue<>();
//        for (ListNode list : lists)
//            if (list != null)
//                heap.offer(list);
//        ListNode dummyHead = new ListNode(0);
//        ListNode prev = dummyHead;
//        while (!heap.isEmpty()) {
//            ListNode tmp = heap.poll();
//            prev.next = tmp;
//            prev = tmp;
//            if (tmp.next != null)
//                heap.offer(tmp.next);
//        }
//        return dummyHead.next;
//    }
//
//    public static int main() {
//        Deque<Integer> stack = new LinkedList<>();
//        char op = '+';
//        int i = 0, n = s.length();
//        char[] ss = s.toCharArray();
//        while (i < n)
//            if (ss[i] == ' ') i++;// 空格
//            else if (ss[i] >= '0' && ss[i] <= '9') {// 数字
//                int tmp = 0;
//                while (i < n && ss[i] >= '0' && ss[i] <= '9') // 多位数
//                    tmp = tmp * 10 + (ss[i++] - '0');
//                if (op == '+') stack.push(tmp);// 不同的运算符，进行不同的计算
//                else if (op == '-') stack.push(-tmp);
//                else if (op == '*') stack.push(stack.pop() * tmp);
//                else if (op == '/') stack.push(stack.pop() / tmp);
//            } else op = ss[i++];// 运算符
//        // int ret = 0;
//        // while (!stack.isEmpty())
//        //     ret += stack.pop();
//        stack.stream().mapToInt(new ToIntFunction<Integer>() {
//            @Override
//            public int applyAsInt(Integer value) {
//                return value;
//            }
//        }).sum();
//        return stack.stream().mapToInt(Integer::intValue).sum();
//    }
//}


import java.util.Collections;

public class Ceshi {
    public static void main(String[] args) {

    }
}




